package org.example.myleet.p909;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 迷宫类型题目
 * 广度优先搜索
 */
public class Solution {

    private int m;

    private int n;

    public int snakesAndLadders(int[][] board) {
        m = board.length;
        n = board[0].length;
        int target = m * n;
        int count = 1;
        boolean[][] visited = new boolean[m][n];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(1);
        while (!stack.isEmpty()) {
            List<Integer> nextSteps = new ArrayList<>();
            while (!stack.isEmpty()) {
                Integer num = stack.pop();
                for (int i = 1; i <= 6; ++i) {
                    int newNum = num + i;
                    if (newNum > m * n) {
                        continue;
                    }
                    int[] newPoint = transform(newNum);
                    if (visited[newPoint[0]][newPoint[1]]) {
                        continue;
                    }
                    visited[newPoint[0]][newPoint[1]] = true;
                    if (board[newPoint[0]][newPoint[1]] != -1) {
                        //遇到蛇或梯子直接传送到下一个点
                        newNum = board[newPoint[0]][newPoint[1]];
                    }
                    if (newNum == target) {
                        return count;
                    }
                    nextSteps.add(newNum);
                }
            }
            for (Integer nextStep : nextSteps) {
                stack.push(nextStep);
            }
            ++count;
        }
        return -1;
    }

    /**
     * 编号转坐标
     */
    private int[] transform(int num) {
        num -= 1;
        int[] point = new int[2];
        int r = num / n;
        point[0] = m - 1 - r;
        point[1] = num % n;
        if ((((m & 1) == 0) && (point[0] & 1) == 0) || (((m & 1) == 1) && (point[0] & 1) == 1)) {
            //编号横向颠倒的行
            point[1] = n - 1 - point[1];
        }
        return point;
    }
}
